package com.ljx.offer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 李捷禧
 * Date: 2023/3/20
 * ClassName: C_54
 */

public class C_54 {
    int res, k;
    public int kthLargest1(TreeNode root, int k) {
        this.k = k;
        dis(root);
        return res;
    }

    /**
     * 思路可以
     * @param root
     */
    void dis(TreeNode root) {
        if(root == null) return;
        dis(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dis(root.left);
    }


    private LinkedList<Integer> list = new LinkedList<>();

    /**
     * 自己写的方法
     * 先排序，在根据索引取出倒数第k个值就是第k大的数
     * @param root
     * @param k
     * @return
     */
    public int kthLargest(TreeNode root, int k) {
        nums(root);
        Collections.sort(list);
        return list.get(list.size() - k);
    }
    void nums(TreeNode root){
            if(root == null) return;
            list.addFirst(root.val);
            nums(root.right);
            nums(root.left);
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
